search game tree
Experiments with some programs that search game trees
Many problems in artificial intelligence involve the searching of large trees of alternative possibilities--for example, game-playing and theorem-proving. The problem of efficiently searching large trees is discussed. A new method called "dynamic ordering" is described, and the older minimax and Alpha-Beta procedures are described for comparison purposes. Performance figures are given for six variations of the game of kalah. A quantity called "depth ratio" is derived which is a measure of the efficiency of a search procedure.